package com.rr.middle;

import java.util.Arrays;

/**
 * @author zhuangcanrun
 * @Date 2022/08/16/19:30
 * @description
 **/

/*
 * https://leetcode.cn/problems/coin-change/
 * 数组题  动态规划
 * */
public class CoinChange {

    public int coinChange(int[] coins, int amount) {
        if (amount <= 0) {
            return 0;
        }
        return getAns(coins, amount, new int[amount]);
    }

    private int getAns(int[] coins, int amount, int[] ints) {
        if (amount < 0) {
            return -1;
        }
        if (amount == 0) {
            return 0;
        }
        if (ints[amount - 1] != 0) {
            return ints[amount - 1];
        }
        int ans = Integer.MAX_VALUE;
        for (int coin : coins) {
            int tmpAns = getAns(coins, amount - coin, ints);
            if (tmpAns >= 0 && tmpAns < ans) {
                ans = tmpAns + 1;
            }
        }

        ints[amount - 1] = (ans == Integer.MAX_VALUE) ? -1 : ans;
        return ints[amount - 1];
    }


    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
        System.out.println(coinChange.coinChange(new int[]{2},3));
    }
}
